﻿/*
 * @autor: hector
 * @date: 26/07/2012
 * @project: Merge2UnsortedArraysWithoutDuplicates
 */

namespace Merge2UnsortedArraysWithoutDuplicates
{
    public static class ArrayExtension
    {
        #region [ First Approach]
        /// <summary>
        /// Merge two unsorted arrays (array1 and array2) in one (sorted) array and removes duplicates
        /// </summary>
        /// <param name="array1">Integer Unsorted Array Values</param>
        /// <param name="array2">Integer Unsorted Array Values</param>
        /// <returns>An sorted integer array</returns>
        internal static int[] MergeWithOutDuplicates(this int[] array1, int[] array2)
        {
            //Merge both arrays
            int[] merged = Merge(array1, array2);
            int[] result = new int[0];
            
            for (int i = 0; i < merged.Length; i++)
            {
                bool AlreadyExists = false;

                for (int j = 0; j < result.Length; j++)
                {
                    //Iterate though both arrays and verify if already exists the number
                    if (merged[i] == result[j])
                    {
                        AlreadyExists = true;
                        break;
                    }
                }

                //If not exists, add the value to the result array
                if (!AlreadyExists)
                    result = Resize(result, merged[i]);
            }

            return result;
        }

        /// <summary>
        /// Sort en ascending order
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        internal static int[] BubbleSort(this int[] input)
        {
            for (int i = 0; i < input.Length; i++)
            {
                for (int j = 0; j < input.Length; j++)
                {
                    if (input[i] > input[j])
                    {
                        int temp = input[i];
                        input[i] = input[j];
                        input[j] = temp;
                    }
                }
            }
            return input;
        }

        /// <summary>
        /// Merges unsorted array1 with unsorted array2 in one unsorted array
        /// </summary>
        /// <param name="array1">Integer unsorted array</param>
        /// <param name="array2">Integer unsorted array</param>
        /// <returns>One unsorted array containing the values of both arrays</returns>
        private static int[] Merge(int[] array1, int[] array2)
        {
            int count = 0;
            int[] merged = new int[array1.Length + array2.Length];

            for (int i = 0; i < array1.Length; i++)
                merged[count++] = array1[i];

            for (int i = 0; i < array2.Length; i++)
                merged[count++] = array2[i];

            return merged;    
        }

        /// <summary>
        /// Resize an array and add the new value
        /// </summary>
        /// <param name="input">Current array</param>
        /// <param name="value">Value to be added</param>
        /// <returns>The current array plus the value</returns>
        private static int[] Resize(int[] input, int value)
        {
            int[] temp = new int[input.Length + 1];

            for (int i = 0; i < input.Length; i++)
                temp[i] = input[i];

            temp[input.Length] = value;

            return temp;
        }
        #endregion

        #region [ Second Approach ]
        internal static int[] MergeWithOutDuplicatesOptimized(this int[] array1, int[] array2)
        {
            
            int length = array1.Length > array2.Length ? array1.Length : array2.Length;

            int[] result = new int[0];
            for (int i = 0; i < length; i++)
            {
                if (i < array1.Length && i<array2.Length)
                {
                    if (array1[i] != array2[i])
                    {
                        result = ResizeOptimized(result, array1[i]);
                        result = ResizeOptimized(result, array2[i]);
                    }                   
                    else if (array1[i] == array2[i])
                    {
                        result = ResizeOptimized(result, array1[i]);
                    }
                }
                else if (i < array1.Length)
                {
                    result = ResizeOptimized(result, array1[i]);
                }
                else if (i <array2.Length)
                {
                    result = ResizeOptimized(result, array2[i]);
                }
            }

            return result;
        }

        private static int[] ResizeOptimized(int[] input, int value)
        {
            if (input.Length == 0)
                return new int[] { value };

            int[] temp = new int[input.Length + 1];

            bool IsAssigned = false;
            int current = int.MinValue;
            
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == value)
                    return input;

                if (value < input[i] && IsAssigned == false)
                {
                    current = input[i];
                    
                    temp[i] = value;
                    temp[i + 1] = current;

                    IsAssigned = true;
                }
                else
                {
                    if (IsAssigned)
                    {
                        temp[i + 1] = input[i];
                    }
                    else
                    {
                        temp[i] = input[i];
                    }

                }
            }

            if(IsAssigned == false)
                temp[input.Length] = value;

            return temp;
        }
        #endregion

        public static int FindDuplicatesOptimized(this int[] input)
        {
            for (int i = 0; i <input.Length; i++)
            {
                for (int k = i,j=input.Length-1; k < input.Length; k++, j--)
                {
                    if (input[i] == input[j])
                    {                        
                        return input[i];
                    }
                    else if (input[i] == input[k])
                    {                        
                        return input[i];
                    }
                    
                }
            }

            return int.MinValue;
        }

        public static int FindDuplicates(this int[] input)
        {
            for (int i = 0; i < input.Length; i++)
            {
                for (int j = i+1; j < input.Length; j++)
                {
                    if (input[i] == input[j])
                    {
                        //System.Console.WriteLine("The duplicated elements are in {0} and {1}: {2}", i, j, input[i]);
                        return input[i];
                    }
                }
            }

            return int.MinValue;
        }

       				

    }
}
